package com.mgq.algorithm.forcerecursive;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import static com.mgq.algorithm.array.InsertSort.swap;

/**
 * @author MaGuangQi
 * 全排列
 * 给一个数组array, 返回总共有多少种排列
 *
 * permute2()返回有多少种, permute3()返回排列的数组
 * 如 array=[1, 2, 3]
 * [1, 2, 3]
 * [1, 3, 2]
 * [2, 1, 3]
 * [2, 3, 1]
 * [3, 2, 1]
 * [3, 1, 2]
 * @date 2022-01-06 17:30
 **/
public class Permutation {
    public static List<List<Integer>> res = new LinkedList<>();


    public static List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> tracks = new LinkedList<>();
        backTrack(nums,tracks);
        return res;
    }

    private static void backTrack(int[] nums, LinkedList<Integer> tracks) {
        //base-case
        if (tracks.size() == nums.length) {
            res.add(new LinkedList<>(tracks));
        }
        //
        for (int i = 0; i < nums.length; i++) {
            //排除不合法的选择
            if (tracks.contains(nums[i])) {
                continue;
            }
            //做选择
            tracks.add(nums[i]);
            //进入下一层决策树
            backTrack(nums,tracks);
            //取消选择
            tracks.removeLast();
        }
    }
    public static int permute2(int[] nums) {
        return process(nums,0);
    }
    //处理i位置的 [0-i-1]已经固定
    //[i....]有多少种
    private  static int result=0;
    public static int process(int[] nums,int i){

        if (i == nums.length) {
            return 1;
        }
        //上面方法是利用了树的深度优先遍历的思想.
        //这个方法是从左到右依次尝试.
        //i后面每一位都需要处理
        for (int j = i; j < nums.length; j++) {
            //j后面的每一位都和i交换.然后处理
            swap(nums,i,j);
            result += process(nums, i + 1);
            //恢复原始数组,继续
            swap(nums,j,i);
        }
       return result;
    }
    public static void permute3(int[] nums) {
         process3(nums,0,new ArrayList<>());
    }
    public static void process3(int[] nums,int i,List<Integer> cur){

        if (i == nums.length) {
             res.add(new LinkedList<>(cur));
        }
        //上面方法是利用了树的深度优先遍历的思想.
        //这个方法是从左到右依次尝试.
        //i后面每一位都需要处理
        for (int j = i; j < nums.length; j++) {
            //j后面的每一位都和i交换.然后处理
            swap(nums,i,j);
            cur.add(nums[i]);
            process3(nums, i + 1,cur);
            //恢复原始数组,继续
            swap(nums,j,i);
            cur.remove(i);
        }

    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        /*permute(nums);

        for (List<Integer> re : res) {
            System.out.println(re);
        }*/
        //System.out.println(permute2(nums));

        permute3(nums);
          for (List<Integer> re : res) {
            System.out.println(re);
        }
    }
}
